get-the-solution

Signal processing

By
on Regards: education; Article; python; sip;

Signal Processing introduction

This text is from the category SIP (Signal and image proccessing).

A signal is defined as any physical or virtual quantity that varies with time or space or any other independent variable.

Expressing a signal in a mathematically way, it can be written as a function of an independent variable which varies for example in time.

Signal in continuous time domain are notated

x(t), 0 ≤ t ≤ T

Signal in discrete time domain are notated

x[n], n = 0, 1,  ·  · ·,N

Signals occur in different environments and are therefore categorized into the continuous time domain and discrete time domain.

Example Signals: Picture file (discrete), audio file (discrete), voltage, speech (continuous), temperature sensor, …

Furthermore some signals are predictable and some or not.

  • Deterministic signal
    • periodically (amplitude characteristics are repeating in time see sinus function)
    • none periodically
      • transient
  • Nondeterministic signal - stationary (probability distribution function or Probability density function are time independent) - non-stationary

Signals

(Fig. 1 discrete x[n] (black) and continues signal x(t)(blue))

There exists infinite types of signals and further more, signals can be composed of each other. Some special signals are that unique that they get there own name and are described in more detail like the Dirac delta function. As mentioned above there exists periodic signals. A signal is periodic if its repeats after a certain number of steps. Think of the sin(x) or cos(x) function.

T...periodic

Discrete signals

Impulse signal - Dirac delta function for discrete signals

The delta function (or impulse signal) is defined for x[0]=1 and for all other position x[n]=0 (where n!=0).

(Fig 2. Dirac delta function or impulse function)

$$\delta[n]=\begin{cases} 1;n=0 \\ 0;otherwise \end{cases} $$

With the delta function its possible to represent, for example the signal x[n] from figure 1, with a sum of delayed and scaled impulses.

Signal transformations

Time shifts using delta function

Transform signal x[n] −  > x[n−n0] where x[n] = delta[n]

See the following example with n0=1:

(Fig 3.)

The signal is shifted to the right by one which causes a delay.

Time reversal

Transform signal x[n] −  > x[−n]

See the following example:

(Fig 4.)

The signal got mirrored.

Scaling using delta function

Transform signal x[n] −  > α ⋅ x[n−n0]; α ∈ ℝ

(Fig 5.)

Even signals

Even signals are defined as x[n] = x[−n] and are symmetric along the Y-Axes.

Odd signals

Odd signals are defined as x[−n] =  − x[n] and are symmetric along the diagonal.

Its always possible to write any signal as a combination of its even and odd parts. Its even parts can be computed by $Even\{x[n]\}=\frac{1}{2}\cdot(x[n]+x[-n])$ and its odds parts by $Odd\{x[n]\}=\frac{1}{2}\cdot(x[n]-x[-n])$.

(Fig 6.)

Basis signal

With the above transformations and signal types we are able to describe signals with the impulse signal (dirac delta function).

See the following example: x[n] = (0,1,2,1,1,0,...)

(Fig 7.)

x[n] = 0 ⋅ δ[n+3] + 1 ⋅ δ[n+2] + 2 ⋅ δ[n+1] + 1 ⋅ δ[n] + 1 ⋅ δ[n−1] + 0 ⋅ δ[n−2] + ...

The above function is now described with explicit terms. We can write more generally:

$x[n]=\sum_{m=\infty}^\infty x[m]\cdot\delta[m-n]$

Sources:

Systems

There exists signal processing systems which can process signals. They consist of a signal input, signal processing unit and signal output (Think of the IPO model).

A common wide known discrete-time system is the linear time-invariant (LTI) System. As the name says its linear and time-invariant Source. Of course there exists other systems which for example are time-variant. Currently we care only about the LTI-system.

This system describes in an abstract way what happens if we input a signal x[n] into a system which outputs y[n]. If the system is not a “black box”, so we know how the system is “responding” the response is often called h[n] (processing unit).

A linear time-invariant system has the following properties:

linearity:

  • put in a signal scaled by coefficient ax1[n] should output ay1[n]
  • put in x1[n]+x2[n] should output y1[n]+y2[n] which means that it got shifted by the same amount as the input

time invariant:

  • shift in time the input x[t-a] should output y[t-a]

This system can be described in generally as y[n]=x[n]*h[n] which is known as the convolution.

(Fig 8.)
(Fig 9.)

Any signal what you can give to a system (x[n]) is just an accumulation of delayed and scaled impulse. So if the LTI response to each of this delayed and scaled impulses with a impulse response h[n], then the output y[n] will be a scaled and delayed sum of impulse response. The formula for computing y[n] is the so called discrete-time convolution (operator asterisk).

General convolution defined by:

y[n] = x[n] * y[n]

Convolution for a one dimensional signal

$y[n]=\sum_{k=\infty}^\infty x[k]\cdot h[n-k]$

The convolution is done in 3 steps:

  • flip one of the two signals

  • shift the flipped signal

  • move it from left to right x axis and calculate the overlapping sum

  • An LTI System is fully characterized by its impulse response

  • The convolution is symmetric x[n] * h[n] = h[n] * x[n]

  • System can also be characterized by difference equalisation

    • (Fig 10.)
    • $y[n]=\sum_{l=1}^N a_l\cdot y[n-l]+\sum_{k=0}^u b_k \cdot x[n-k]$
    • Often used when system impulse response is infinite

For the online convolution calculator click here

2d convolution is used for example in image processing. For more details checkout http://www.songho.ca/dsp/convolution/convolution.html#convolution_2d

System accumulator

$y[n]=\sum_{k=-\infty}^n x[k]$

Property stable system

LTI systems are stable if the absolute sum of there impulse response is finite.

$y[n]=\sum_{n=-\infty}^\infty |h[n]| < \infty$

Property causal system

We call a system causal iff h[n] = 0, ∀n < 0

Example in fig 10 shows h[n] as causal and h`[n] as acausal.

(Fig 11.)

Discrete (time) Fourier Transform

The Fourier transformation is named after Jean Baptiste Joseph Fourier (1768-1830), a French mathematician and physicist. His paper regarding the fourier transformation paper contained that any continuous periodic signal could be represented as the sum of properly chosen sinusoidal waves. This means that when applying the DFT to a signal, it assumes that the signal is periodic.

As a signal can be continuous or discrete and signals can be periodic or aperiodic will result in up to four categories. Lets focus on the discrete fourier transformation which is relevant for discret and periodic signals. [Source: The Scientist and Engineer’s Guide to Digital Signal Processing]

With the discrete fourier transform signals can be transformed from real numbers (time domain) to the complex numbers (frequency domain). The transformation process from time domain to frequency domain is called decomposition, analysis or the forward DFT. Transforming from the frequency domain to the time domain is called synthesis, or the inverse DFT. Using the dft can help to perform certain task easier and do for example frequency domain analysis, compress signals or apply filters to signal (remove unwanted noise or filter for certain signal of interest).

A discrete signal in the time domain can be written as vector for example:

x[n]=(0,1,2,1,0,-1,-2,-1) N=8.

(Fig 12. signal of x[n])

This signal of it can be rewritten as a sum of delta impulses as basis with its coefficients (linear combination with basis elements):

x[n] = 0 ⋅ δ[n] + 1 ⋅ δ[n−1] + 2 ⋅ δ[n−2] + 2 ⋅ δ[n−2] + ...

Bases allow one to represent vectors by a sequence of scalars called coordinates or components Source.

In the frequency domain the k-th basis vector is a complex vector (where 0 ≤ k ≤ N − 1) defined as

$b_k[n]:=exp(j\frac{2\pi\cdot k}{N}\cdot n)$

The basis vectors bk represent oscillations. We can write the signal using the basis vectors bk the same way as we did with the delta impulses. The coordinates X[k], with respect to this basis, can be calculated using the following equation (By convention the frequency domain is using Uppercase letters.):

$X[k]=\sum_{n=0}^{N-1} x[n]\cdot e^{-j\cdot\frac{2\pi\cdot k}{N}\cdot n} \qquad(analysis, dft, decomposition)$

To transform not only the k-th element to the spectrum domain we need to compute discrete fourier transform over the whole vector with:

X = (X[0],X[1],X[2],...,X[N])

This means for the transformed X there exists N unique frequencies.

Moving back from the frequency domain to the time domain can be accomplished with:

$x[n]=\frac{1}{N}\cdot \sum_{k=0}^{N-1} X[k]\cdot e^{j\cdot\frac{2\pi\cdot k}{N}\cdot n} \qquad(inverse dft, synthesis)$

This gives us the ability to reconstruct with the inverse dft the complete original signal.

For the signal of figure 12 we would do the following to calculate the dft.

x[n] = (0,1,2,1,0,−1,−2,−1)N = 8

$X[k]=\sum_{n=0}^{N-1} x[n]\cdot e^{-j\cdot\frac{2\pi\cdot k}{N}\cdot n} \qquad(analysis, dft, decomposition)$

$X[0]=\sum_{n=0}^{7} x[n]\cdot e^{-j\cdot\frac{2\pi\cdot 0}{8}\cdot n}=0\cdot e^0+ 1\cdot e^0+ 2\cdot e^0+ 1\cdot e^0+ 0\cdot e^0- 1\cdot e^0- 2\cdot e^0- 1\cdot e^0=0$

$X[1]=\sum_{n=0}^{7} x[n]\cdot e^{-j\cdot\frac{2\pi\cdot 1}{8}\cdot n}=0\cdot e^{-j\cdot\frac{2\pi\cdot 1}{8}\cdot 0}+1\cdot e^{-j\cdot\frac{2\pi\cdot 1}{8}\cdot 1}+2\cdot e^{-j\cdot\frac{2\pi\cdot 1}{8}\cdot 2}+1\cdot e^{-j\cdot\frac{2\pi\cdot 1}{8}\cdot 3}+...=0-6.82843i$

X[2] = 0

X[...] = ...

X[7] = 0 + 6.8284i

X=(0+0i, 0-6.8284i, -0+0i, -0+1.1716i,0+0i, 0-1.1716i, 0+0i, 0+6.8284i)

There are some common representations for the transformed signal which are often called Amplitude, Magnitude or Spectrum. The spectrum shows all frequencies which the signal contains and is calculated with $\sphericalangle X(e^{j\omega})=arctan(\frac{Img\{H(e^{j\omega})\}}{Re\{H(e^{j\omega})\}})$. The Magnitude is the absolute value of any value, as opposed to its phase. For example the absolute value of $|H(e^{j\omega})|=\sqrt{Re\{H(e^{j\omega})\}^2+Img\{H(e^{j\omega})\}^2}$.

Sources: “Understanding Digital Signal Processing” by Richard G. Lyons, Chapter 1.2 Signal Amplitude, Magnitude, Power

The amplitude can be calculated using the absolute value of the complex numbers of X.

X(amplitude)=(0, 6.8284, 4.4435e-16, 1.1715, 9.8607e-32, 1.1715, 3.8377e-15, 6.8284)

The phase can be calculated from the complex numbers of X.

X(phase)=( 0., -1.570796, 1.605601, 1.570796, 1.570796, -1.570796, 0.35452 , 1.570796)

(Fig 13. amplitude and phase)

Yet, we dealed with discrete signals (= frequency and time are discrete). For the case where the time is discrete but the frequency is continuos we use the term discrete-time (= time is discrete, frequency is continuous). The discrete fourier transformation for the discrete-time is defined as the following:

Letting N −  > ∞, we obtain the discrete-time fourier transformation (frequency is continuous)

$X(\omega)=\sum_{\infty}^{n=-\infty} x[n]\cdot e^{-j\cdot\omega\cdot n}, \omega \in [0,2\pi] \qquad(analysis, dft, decomposition)$

$x[n]=\frac{1}{2\pi}\cdot \int_{-\pi}^{\pi} X(\omega)\cdot e^{j\cdot\omega\cdot n} d\omega \qquad(inverse dft, synthesis)$

Summary:

  • DFT and inverse DFT transform between time and frequency domain without loss of information
  • DFT is not optimal for aperiodic signals - will result in artifacts - transient events (signal which occurs only in a certain time frame is also known as transient signal)
Periodic Non-periodioc
Discrete Time DT Fourier Series DT Fourier Transform
DT analysis $X[k]=\sum_{n=0}^{N-1} x[n]\cdot e^{-j\cdot\frac{2\pi\cdot k}{N}\cdot n}$ $X(\omega)=\sum_{\infty}^{n=-\infty} x[n]\cdot e^{-j\cdot\omega\cdot n}, \omega \in [0,2\pi]$
DT synthesis $x[n]=\frac{1}{N}\cdot \sum_{k=0}^{N-1} X[k]\cdot e^{j\cdot\frac{2\pi\cdot k}{N}\cdot n}$ $x[n]=\frac{1}{2\pi}\cdot \int_{-\pi}^{\pi} X(\omega)\cdot e^{j\cdot\omega\cdot n} d\omega$

Properties of Discrete Fourier Transform

Parseval’s theorem

The energy in both Domains (time and frequency) is the same

$\underbrace{\sum_{\infty}^{n=-\infty}| x[n] |^2}_{\substack{energy\\time\\domain}} =\underbrace{\frac{1}{2\cdot\pi}\int_{-\pi}^{\pi} |X(\omega)|^2 d\omega}_{\substack{energy\\frequency\\domain}}$

Parseval’s theorem wiki

Convolution theorem

“More generally, convolution in one domain (e.g., time domain) equals point-wise multiplication in the other domain (e.g., frequency domain)” [Source https://en.wikipedia.org/wiki/Convolution_theorem]

DTFT{h[n] * x[n]} = H(ω) ⋅ X(ω)

Modulation theorem

The modulation theorem is some kind of a inverse convolution theorem. convolution in time domain is equivalent to a multiplication in frequency domain.
multiplication in the time domain it will be a convolution in the frequency domain. multiplication in one domain is convolution in the other domain and visa verse.

DTFT{h[n] ⋅ x[n]} = H(ω) * X(ω)

Symmetries in the D(T)FT

X(ω) = X(−ω)*

|X(ω)| = |X(−ω)|

∢X(ω) =  − ∢X(−ω)

for real valued signals the amplitudes of the negative frequencies are the same as the positive frequencies and the phases are symmetric. that means the positive frequencies contains all information about the spectrum.

Continue to Sampling

Sources: